import java.util.HashMap;
import java.util.Stack;

/**
 * Implement a basic calculator to evaluate a simple expression string.

The expression string contains only non-negative integers, +, -, *, / operators and empty spaces . The integer division should truncate toward zero.

You may assume that the given expression is always valid.

Some examples:
"3+2*2" = 7
" 3/2 " = 1
" 3+5 / 2 " = 5
 * @author Jingjing Wang
 *2015-6-28
 */
public class BasicCalculator {

	public static void main(String[] args) {
		String expression = "1+2*5/3+6/4*2";
		System.out.println(Integer.MAX_VALUE);
		BasicCalculator calculator = new BasicCalculator();
		System.out.println(calculator.calculate(expression));
	}

	public int calculate(String s) {
		HashMap<String, Integer> operation2Priority = new HashMap<String, Integer>();
		operation2Priority.put("*", 2);
		operation2Priority.put("/", 2);
		operation2Priority.put("+", 1);
		operation2Priority.put("-", 1);

		s = s.replace(" ", "");
		String[] numbersString = s.split("[\\+ | \\- | \\* | \\/]");
		String[] operations = s.split("[0-9]+");
		if (operations.length == 0) {
			return (int) Long.parseLong(s);
		}

		Stack<Long> numbers = new Stack<Long>();
		Stack<String> calcution = new Stack<String>();
		int numIndex = 0;
		int oprationIndex = 1;
		long num1, num2, result;
		boolean hasToken = false;

		while (numIndex < numbersString.length
				&& oprationIndex < operations.length) {
			if (!hasToken) {
				numbers.push(Long.parseLong(numbersString[numIndex++]));
			} else {
				hasToken = false;
			}

			String currentOperation = operations[oprationIndex++];
			if (calcution.isEmpty()) {
				calcution.push(currentOperation);
			} else if (operation2Priority.get(calcution.peek()) >= operation2Priority
					.get(currentOperation)) { // previous */ , current
												// +-
				num2 = numbers.pop();
				num1 = numbers.pop();
				result = calc(calcution.pop(), num1, num2);

				numbers.push(result);
				calcution.push(currentOperation);
			} else { // prev +- ,current */
				hasToken = true;
				num2 = Long.parseLong(numbersString[numIndex++]);
				num1 = numbers.pop();
				result = calc(currentOperation, num1, num2);
				numbers.push(result);
			}
		}

		if (numIndex == numbersString.length - 1) {
			num2 = Long.parseLong(numbersString[numIndex]);
			return (int) calc(calcution.pop(), numbers.pop(), num2);
		} else {
			num2 = numbers.pop();
			num1 = numbers.pop();
			return (int) calc(calcution.pop(), num1, num2);
		}
	}

	public long calc(String operation, long num1, long num2) {
		switch (operation) {
		case "+":
			return num1 + num2;
		case "-":
			return num1 - num2;
		case "*":
			return num1 * num2;
		case "/":
			return num1 / num2;

		default:
			return 0;
		}
	}
}
